package com.chen.forum.controller;

public class KMP {
    public static void main(String[] args) {
        System.out.println(kmp("abcdhjkhfhfh", "bbdbbse"));
    }

    public static int kmp(String s1, String m1) {
        char[] str = s1.toCharArray();
        char[] match = m1.toCharArray();
        int[] next = getNextArray(match);
        int i = 0;
        int x = 0;
        while (i < str.length && x < match.length) {
            if (str[i] == match[x]) {
                i++;
                x++;
            } else if (x > 0) {
                x = next[x];
            } else {
                i++;
            }
        }
        return x == match.length ? i - x : -1;
    }

    public static int[] getNextArray(char[] arr) {
        if (arr.length == 1) {
            return new int[]{-1};
        }
        int[] res = new int[arr.length];
        res[0] = -1;
        res[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < arr.length) {
            if (arr[i - 1] == arr[cn]) {
                res[i++] = ++cn;
            } else if (cn > 0) {
                cn = res[cn];
            } else {
                res[i++] = 0;
            }
        }
        return res;
    }
}
